// 给定一个数组nums，nums是升序数组经过旋转得到的，但是旋转次数未知，数组中可能存在重复元素,要求找出数组中的最小元素

// 思路：数组经过旋转后会有两种情况：1. 原先的升序序列， 2. 两端升序的序列，第一种的最小值在最左边， 第二种最小值在第二段升序序列的第一个元素
// left和right分别指向数组的首尾，计算中间值mid
// 如果nums[mid] > nums[right]，最小值一定在mid右侧，left移到mid + 1，查找右侧区间
// 如果nums[mid] === nums[right]， right向前移动一位，缩小区域
// 如果nums[mid] < nums[right]，最小值一定在mid左侧，将right移动到mid位置，查找左侧区间

function findMin(nums) {
    let left = 0
    let right = nums.length - 1
    while (left < right) {
        let mid = Math.floor((right - left) / 2) + left
        if (nums[mid] > nums[right]) {
            left = mid + 1
        } else if (nums[mid] < nums[right]) {
            right = mid
        } else {
            right = right - 1
        }
    }
    return nums[left]
}

let arr = [3, 4, 5, 1, 1, 2, 2, 3]
console.log(findMin(arr));